{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Letter Case Permutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: letterCasePermutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字母大小写全排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串&nbsp;<code>s</code>&nbsp;，通过将字符串&nbsp;<code>s</code>&nbsp;中的每个字母转变大小写，我们可以获得一个新的字符串。</p>\n",
    "\n",
    "<p>返回 <em>所有可能得到的字符串集合</em> 。以 <strong>任意顺序</strong> 返回输出。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"a1b2\"\n",
    "<strong>输出：</strong>[\"a1b2\", \"a1B2\", \"A1b2\", \"A1B2\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"3z4\"\n",
    "<strong>输出:</strong> [\"3z4\",\"3Z4\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 12</code></li>\n",
    "\t<li><code>s</code>&nbsp;由小写英文字母、大写英文字母和数字组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [letter-case-permutation](https://leetcode.cn/problems/letter-case-permutation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [letter-case-permutation](https://leetcode.cn/problems/letter-case-permutation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"a1b2\"', '\"3z4\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        permutations = []\n",
    "        permutations.append(s)\n",
    "        for i in range(len(s)):\n",
    "            if s[i].isalpha():\n",
    "                n = len(permutations)\n",
    "                for j in range(n):\n",
    "                    chs = list(permutations[j])\n",
    "                    chs[i] = chs[i].swapcase()\n",
    "                    permutations.append(''.join(chs))\n",
    "        return permutations\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        def dfs(s, pos):\n",
    "            while pos<len(s) and s[pos].isdigit():\n",
    "                pos += 1\n",
    "            if pos == len(s):\n",
    "                ans.append(''.join(s))\n",
    "                return \n",
    "            dfs(s, pos+1)\n",
    "            s[pos] = s[pos].swapcase()\n",
    "            dfs(s, pos+1)\n",
    "            s[pos] = s[pos].swapcase()\n",
    "        dfs(list(s), 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        def dfs(path, i):\n",
    "            if i == len(s):\n",
    "                ans.append(path)\n",
    "                return\n",
    "\n",
    "            dfs(path + s[i], i + 1)\n",
    "            if ord('a') <= ord(s[i]) <= ord('z'):\n",
    "                dfs(path + s[i].upper(), i + 1)\n",
    "            elif ord('A') <= ord(s[i]) <= ord('Z'):\n",
    "                dfs(path + s[i].lower(), i + 1)\n",
    "        ans, path = [], \"\"\n",
    "        dfs(path, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = [\"\"]\n",
    "        for i, c in enumerate(s):\n",
    "            if c.isalpha():\n",
    "                ans = [a + c.lower() for a in ans] + [a + c.upper() for a in ans]\n",
    "            else:\n",
    "                ans = [a + c for a in ans]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> [str]:\n",
    "        nn=0\n",
    "        dp=[]\n",
    "        di=defaultdict()\n",
    "        for i in range(len(s)):\n",
    "            if s[i].isdigit(): pass\n",
    "            else:\n",
    "                nn+=1\n",
    "                dp.append(i)\n",
    "                di[i]=nn-1\n",
    "\n",
    "        ans=[]\n",
    "        tot=1<<nn\n",
    "        for i in range(tot):\n",
    "            ss=''\n",
    "            for k in range(len(s)):\n",
    "                if s[k].islower():\n",
    "                    if i&(1<<di[k]):\n",
    "                        ss=ss+chr(ord(s[k])-ord('a')+ord('A'))\n",
    "                    else:\n",
    "                        ss = ss + s[k]\n",
    "                elif s[k].isupper():\n",
    "                    if i & (1 << di[k]):\n",
    "                        ss = ss + chr(ord(s[k]) - ord('A') + ord('a'))\n",
    "                    else:\n",
    "                        ss = ss + s[k]\n",
    "                else:\n",
    "                    ss=ss+s[k]\n",
    "\n",
    "            ans.append(ss)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        n = sum(c.isalpha() for c in s)\n",
    "        for i in range(1 << n):\n",
    "            j, t = 0, []\n",
    "            for c in s:\n",
    "                if c.isalpha():\n",
    "                    c = c.lower() if (i >> j) & 1 else c.upper()\n",
    "                    j += 1\n",
    "                t.append(c)\n",
    "            ans.append(''.join(t))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        self.ans = []\n",
    "        self.recur(list(s),0)\n",
    "        return self.ans\n",
    "    \n",
    "    def recur(self,string,index):\n",
    "        if index == len(string):\n",
    "            self.ans.append(''.join(string))\n",
    "            return\n",
    "        \n",
    "        if string[index].isnumeric():\n",
    "            self.recur(string,index+1)\n",
    "        else:\n",
    "            string[index] = string[index].lower()\n",
    "            self.recur(string,index+1)\n",
    "            string[index] = string[index].upper()\n",
    "            self.recur(string,index+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        res = ['']\n",
    "        for i in range(len(s)):\n",
    "            if s[i].isdigit():\n",
    "                for j in range(len(res)):\n",
    "                    res[j] += s[i]\n",
    "            if s[i].isalpha():\n",
    "                n = len(res)\n",
    "                for j in range(n):\n",
    "                    tmp = res.pop(0)\n",
    "                    res.append(tmp+s[i].lower())\n",
    "                    res.append(tmp+s[i].upper())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\r\n",
    "        s=list(s)\r\n",
    "        n=len(s)\r\n",
    "        last=['']\r\n",
    "        for i in s:\r\n",
    "            now=last\r\n",
    "            last=[]\r\n",
    "            for j in now:\r\n",
    "                if i.isalpha():\r\n",
    "                    last.append(j+i.lower())\r\n",
    "                    last.append(j+i.upper())\r\n",
    "                else:\r\n",
    "                    last.append(j+i)\r\n",
    "        return last\r\n",
    "        \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        m = sum(c.isalpha() for c in s)\n",
    "        for mask in range(1 << m):\n",
    "            t, k = [], 0\n",
    "            for c in s:\n",
    "                if c.isalpha():\n",
    "                    t.append(c.upper() if mask >> k & 1 else c.lower())\n",
    "                    k += 1\n",
    "                else:\n",
    "                    t.append(c)\n",
    "            ans.append(''.join(t))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        m = sum(c.isalpha() for c in s)\n",
    "        for mask in range(1 << m):\n",
    "            t, k = [], 0\n",
    "            for c in s:\n",
    "                if c.isalpha():\n",
    "                    t.append(c.upper() if mask >> k & 1 else c.lower())\n",
    "                    k += 1\n",
    "                else:\n",
    "                    t.append(c)\n",
    "            ans.append(''.join(t))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        q = collections.deque([''])\n",
    "        while q:\n",
    "            cur = q[0]\n",
    "            pos = len(cur)\n",
    "            if pos == len(s):\n",
    "                ans.append(cur)\n",
    "                q.popleft()\n",
    "            else:\n",
    "                if s[pos].isalpha():\n",
    "                    q.append(cur + s[pos].swapcase())\n",
    "                q[0] += s[pos]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        def dfs(state, start, res):\n",
    "            print(state)\n",
    "            if start == len(s):\n",
    "                res.append(str(state))\n",
    "                return\n",
    "            if s[start].isdigit():\n",
    "                state += s[start]\n",
    "                dfs(state, start + 1, res)\n",
    "            else:\n",
    "                state += s[start].lower()\n",
    "                dfs(state, start + 1, res)\n",
    "                state = state[:-1]\n",
    "                state += s[start].upper()\n",
    "                dfs(state, start + 1, res)\n",
    "        res = []\n",
    "        dfs('', 0, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,s,path,result,i):\n",
    "        if i==len(path):\n",
    "            result.append(''.join(path))\n",
    "            return\n",
    "\n",
    "        self.dfs(s,path,result,i+1)\n",
    "        if path[i].isalpha():\n",
    "            path[i]=path[i].swapcase()\n",
    "            self.dfs(s,path,result,i+1)\n",
    "\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        result=[]\n",
    "        path=list(s)\n",
    "        self.dfs(s,path,result,0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s1: str) -> List[str]:\n",
    "        def isLetter(ch):\n",
    "            return 'a' <= ch <= 'z' or 'A' <= ch <= 'Z'\n",
    "        ans = []\n",
    "        n, m = len(s1), len([ch for ch in s1 if isLetter(ch)])\n",
    "        for s in range(1 << m):\n",
    "            cur = ''\n",
    "            j = 0\n",
    "            for i in range(n):\n",
    "                if not isLetter(s1[i]) or not ((s >> j) & 1):\n",
    "                    cur += s1[i]\n",
    "                else:\n",
    "                    cur += s1[i].swapcase()\n",
    "                if isLetter(s1[i]):\n",
    "                    j += 1\n",
    "            ans.append(cur)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        s = s.lower()\n",
    "        if s[0].isalpha():\n",
    "            que1 = [s[0], s[0].upper()]\n",
    "        else:\n",
    "            que1 = [s[0]]\n",
    "        \n",
    "        for i in range(1, len(s)):\n",
    "            if s[i].isalpha():\n",
    "                for qi in range(len(que1)):\n",
    "                    qq = que1[qi]\n",
    "                    que1[qi] = qq + s[i]\n",
    "                    que1.append(qq + s[i].upper())\n",
    "            else:\n",
    "                for qi in range(len(que1)):\n",
    "                    que1[qi] = que1[qi] + s[i]\n",
    "        return que1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        s = s.lower()\n",
    "        def letter_case_permutation(s):\n",
    "            if not s:\n",
    "                return [\"\"]\n",
    "            else:\n",
    "                first = s[0]\n",
    "                rest = letter_case_permutation(s[1:])\n",
    "                if first.isalpha():\n",
    "                    return [first.lower() + r for r in rest] + [first.upper() + r for r in rest]\n",
    "                else:\n",
    "                    return [first + r for r in rest]\n",
    "        return letter_case_permutation(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        if len(s)==0:\n",
    "            return []\n",
    "        \n",
    "        result=['']\n",
    "        for c in s:\n",
    "            tmp=result\n",
    "            result=[]\n",
    "            for strs in tmp:\n",
    "                if c.isalpha():\n",
    "                    result.append(strs+c.lower())\n",
    "                    result.append(strs+c.upper())\n",
    "                else:\n",
    "                    result.append(strs+c)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans=[]\n",
    "        q=deque([''])\n",
    "        while q:\n",
    "            cur=q[0]\n",
    "            pos=len(cur)\n",
    "            if pos == len(s):\n",
    "                ans.append(cur)\n",
    "                q.popleft()\n",
    "            else:\n",
    "                if s[pos].isalpha():\n",
    "                    q.append(cur+s[pos].swapcase())\n",
    "                q[0]+=s[pos]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        if not s:\n",
    "            return []\n",
    "        else:\n",
    "            res = self.expend(s[0])\n",
    "            for i in range(1, len(s)):\n",
    "                target = self.expend(s[i])\n",
    "                res = [''.join(r) for r in product(res, target)]\n",
    "        return res\n",
    "    \n",
    "\n",
    "    def expend(self, letter: str) -> List[str]:\n",
    "        if letter.isalpha():\n",
    "            return [letter.upper(), letter.lower()]\n",
    "        return [letter]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = [\"\"]\n",
    "        for i, c in enumerate(s):\n",
    "            if c.isalpha():\n",
    "                ans = [a + c.lower() for a in ans] + [a + c.upper() for a in ans]\n",
    "            else:\n",
    "                ans = [a + c for a in ans]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = [\"\"]\n",
    "        for i, c in enumerate(s):\n",
    "            if c.isalpha():\n",
    "                ans = [a + c.lower() for a in ans] + [a + c.upper() for a in ans]\n",
    "            else:\n",
    "                ans = [a + c for a in ans]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "\n",
    "        arr = list(s)\n",
    "        self.dfs(0, arr, res)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, ind, word, ret):\n",
    "\n",
    "        while ind < len(word) and word[ind].isdigit():\n",
    "            ind += 1\n",
    "        \n",
    "        if ind == len(word):\n",
    "            ret.append(\"\".join(word))\n",
    "            return\n",
    "        \n",
    "        self.dfs(ind + 1, word, ret)                  # invert and search forward\n",
    "        word[ind] = word[ind].swapcase()\n",
    "\n",
    "        self.dfs(ind + 1, word, ret)\n",
    "        word[ind] = word[ind].swapcase()              # recover word\n",
    "\n",
    "\"\"\" \n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        def dfs(s: List[str], pos: int) -> None:\n",
    "            while pos < len(s) and s[pos].isdigit():\n",
    "                pos += 1\n",
    "            if pos == len(s):\n",
    "                ans.append(''.join(s))\n",
    "                return\n",
    "            dfs(s, pos + 1)\n",
    "            s[pos] = s[pos].swapcase()\n",
    "            dfs(s, pos + 1)\n",
    "            s[pos] = s[pos].swapcase()\n",
    "        dfs(list(s), 0)\n",
    "        return ans\n",
    "\"\"\" \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        q,r=collections.deque(['']),[]\n",
    "        while q:\n",
    "            if len(q[0])==len(s):r.append(q.popleft())\n",
    "            else:\n",
    "                if s[len(q[0])].isalpha():q.append(q[0]+s[len(q[0])].swapcase())\n",
    "                q[0]+=s[len(q[0])]\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        result = []\n",
    "        ln = len(s)\n",
    "        def backtracking(index: int, temp: list[str]):\n",
    "            if index == ln:\n",
    "                result.append(\"\".join(temp))\n",
    "                return\n",
    "            \n",
    "            temp.append(s[index])\n",
    "            backtracking(index + 1, temp)\n",
    "            temp.pop()\n",
    "            \n",
    "            if s[index].isalpha():\n",
    "                temp.append(s[index].swapcase())\n",
    "                backtracking(index + 1, temp)\n",
    "                temp.pop()\n",
    "\n",
    "        backtracking(0, [])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        def dfs(state, start, res):\n",
    "            if start == len(s):\n",
    "                res.append(str(state))\n",
    "                return\n",
    "            if s[start].isdigit():\n",
    "                state += s[start]\n",
    "                dfs(state, start + 1, res)\n",
    "            else:\n",
    "                state += s[start].lower()\n",
    "                dfs(state, start + 1, res)\n",
    "                state = state[:-1]\n",
    "                state += s[start].upper()\n",
    "                dfs(state, start + 1, res)\n",
    "        res = []\n",
    "        dfs('', 0, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        # 子集问题\n",
    "        reslist = []\n",
    "        s_list = list(s)\n",
    "        def backtracking(reslist, s_list, startIndex):\n",
    "            reslist.append(\"\".join(s_list))\n",
    "            for i in range(startIndex, len(s_list)):\n",
    "                if s_list[i].isalpha():\n",
    "                    if s_list[i].isupper():\n",
    "                        s_list[i] = s_list[i].lower()\n",
    "                        backtracking(reslist, s_list, i + 1)\n",
    "                        s_list[i] = s_list[i].upper()\n",
    "                    else:\n",
    "                        s_list[i] = s_list[i].upper()\n",
    "                        backtracking(reslist, s_list, i + 1)\n",
    "                        s_list[i] = s_list[i].lower()\n",
    "        backtracking(reslist, s_list, 0)\n",
    "        return reslist\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        result=['']\n",
    "        for c in s:\n",
    "            tmp=result\n",
    "            result=[]\n",
    "            for strs in tmp:\n",
    "                if c.isalpha():\n",
    "                    result.append(strs+c.lower())\n",
    "                    result.append(strs+c.upper())\n",
    "                else:\n",
    "                    result.append(strs+c)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        path = []\n",
    "\n",
    "        def dfs(i: int) -> None:\n",
    "            if i == n:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "\n",
    "            c = s[i]\n",
    "            path.append(c)\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "\n",
    "            if 'a' <= c <= 'z':\n",
    "                path.append(chr(ord(c) - 32))\n",
    "                dfs(i + 1)\n",
    "                path.pop()\n",
    "\n",
    "            if 'A' <= c <= 'Z':\n",
    "                path.append(chr(ord(c) + 32))\n",
    "                dfs(i + 1)\n",
    "                path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        q = deque([''])\n",
    "        while q:\n",
    "            cur = q[0]\n",
    "            pos = len(cur)\n",
    "            if pos == len(s):\n",
    "                ans.append(cur)\n",
    "                q.popleft()\n",
    "            else:\n",
    "                if s[pos].isalpha():\n",
    "                    q.append(cur + s[pos].swapcase())\n",
    "                q[0] += s[pos]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, _str: str):\n",
    "        stack = []\n",
    "        path = []\n",
    "        isvisited = []\n",
    "        strs = []\n",
    "        stack.insert(-1,[_str[0],\"\"])\n",
    "        while stack != []:\n",
    "            item,path = stack.pop()\n",
    "            if path not in isvisited:\n",
    "                isvisited.append(path)\n",
    "                for next_item,next_path in self.next_state(path,_str):\n",
    "                    stack.insert(-1,[next_item,next_path])\n",
    "        return list(filter( lambda x:len(x) == len(_str),isvisited))\n",
    "        \n",
    "    def next_state(self,path,_str):\n",
    "        if len(path) == len(_str):\n",
    "            return [([],\"\")]\n",
    "        item = _str[len(path)]\n",
    "        if item.isalpha():\n",
    "            return [(item.lower(),path+item.lower()),(item.upper(),path+item.upper())]\n",
    "        else:\n",
    "            return [(item,path+item)]\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    _str = \"a1b2\"\n",
    "    b = Solution()\n",
    "    print(b.letterCasePermutation(_str))\n",
    "    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        result = []\n",
    "        queue = deque([''])\n",
    "        while queue:\n",
    "            curr = queue[0]\n",
    "            pos = len(curr)\n",
    "            if pos == len(s):\n",
    "                result.append(curr)\n",
    "                queue.popleft()\n",
    "            else:\n",
    "                if s[pos].isalpha():\n",
    "                    queue.append(curr + s[pos].swapcase())\n",
    "                queue[0] += s[pos]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "\n",
    "        res = []\n",
    "        path = []\n",
    "        n = len(s)\n",
    "        \n",
    "        def dfs(i: int):\n",
    "            if i == n:\n",
    "                res.append(''.join(path))\n",
    "                return\n",
    "            \n",
    "            if s[i].isdigit():\n",
    "                path.append(s[i])\n",
    "                dfs(i + 1)\n",
    "                path.pop()\n",
    "            else:\n",
    "                path.append(s[i])\n",
    "                dfs(i + 1)\n",
    "                path.pop()\n",
    "\n",
    "                path.append(s[i].swapcase())\n",
    "                dfs(i + 1)\n",
    "                path.pop()  \n",
    "               \n",
    "        \n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        if len(s) is 0:\n",
    "            return ['']\n",
    "        ans = []\n",
    "        c = s[0]\n",
    "        for _, x in enumerate(self.letterCasePermutation(s[1:])):\n",
    "           ans.append(c + x)\n",
    "           if c >= 'A' and c <= 'z':\n",
    "                if c >= 'A' and c <= 'Z':\n",
    "                    ans.append(c.lower() + x)\n",
    "                else:\n",
    "                    ans.append(c.upper() + x)       \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        n=len(s)\n",
    "        ans=[]\n",
    "        path=['']*n\n",
    "\n",
    "        def dfs(i:int)->None:\n",
    "            if i==n:\n",
    "                ans.append(\"\".join(path))\n",
    "                return\n",
    "            path[i]=s[i]\n",
    "            dfs(i+1)\n",
    "            if s[i].isalpha():\n",
    "                path[i]=s[i].swapcase()\n",
    "                dfs(i+1)\n",
    "        dfs(0)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        path=[]\n",
    "        result=[]\n",
    "        self.backwards(s, path, result, 0)\n",
    "        return list(set(result))\n",
    "    \n",
    "    def backwards(self,s,path,result,idx):\n",
    "        if len(path)==len(s):\n",
    "            result.append(''.join(path[:]))\n",
    "        for j in range(2):\n",
    "            for i in range(idx,len(s)):\n",
    "                if j==0 and s[i].isalpha():\n",
    "                    if s[i].isupper():\n",
    "                        path.append(s[i].lower())\n",
    "                    else:\n",
    "                        path.append(s[i].upper())\n",
    "                else:\n",
    "                    path.append(s[i])\n",
    "                self.backwards(s, path, result, i+1)\n",
    "                path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "\n",
    "        def dfs(start: int, stack: list, ans: list) -> None:\n",
    "            if len(stack) == n:\n",
    "                ans.append(''.join(stack[:]))\n",
    "                return\n",
    "            \n",
    "            for i in range(start, n):\n",
    "                ch = s[i]\n",
    "                \n",
    "                if  'a' <= ch <= 'z':\n",
    "                    stack.append(ch)\n",
    "                    dfs(i + 1, stack, ans)\n",
    "                    stack.pop(-1)\n",
    "\n",
    "                    stack.append(ch.upper())\n",
    "                    dfs(i + 1, stack, ans)\n",
    "                    stack.pop(-1)\n",
    "\n",
    "                elif 'A' <= ch <= 'Z':\n",
    "                    stack.append(ch)\n",
    "                    dfs(i + 1, stack, ans)\n",
    "                    stack.pop(-1)\n",
    "\n",
    "                    stack.append(ch.lower())\n",
    "                    dfs(i + 1, stack, ans)\n",
    "                    stack.pop(-1)\n",
    "\n",
    "                else:\n",
    "                    stack.append(ch)\n",
    "                    dfs(i + 1, stack, ans)\n",
    "                    stack.pop(-1)\n",
    "\n",
    "        ans = []\n",
    "        dfs(0, [], ans)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, _str: str):\n",
    "        stack = []\n",
    "        path = []\n",
    "        isvisited = []\n",
    "        stack.insert(-1,\"\")\n",
    "        while stack != []:\n",
    "            path = stack.pop()\n",
    "            if path not in isvisited:\n",
    "                isvisited.append(path)\n",
    "                for next_path in self.next_state(path,_str):\n",
    "                    stack.insert(-1,next_path)\n",
    "        return list(filter( lambda x:len(x) == len(_str),isvisited))\n",
    "        \n",
    "    def next_state(self,path,_str):\n",
    "        if len(path) == len(_str):\n",
    "            return [\"\"]\n",
    "        item = _str[len(path)]\n",
    "        if item.isalpha():\n",
    "            return [path+item.lower(),path+item.upper()]\n",
    "        else:\n",
    "            return [path+item]\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    _str = \"a1b2\"\n",
    "    b = Solution()\n",
    "    print(b.letterCasePermutation(_str))\n",
    "    \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        # res = set()\n",
    "        # for i,r in enumerate(s):\n",
    "        #     if r.isalpha():\n",
    "        #         rr = r[:]\n",
    "        #         res.add(s[:i]+rr.lower()+s[i+1:])\n",
    "        #         res.add(s[:i]+rr.upper()+s[i+1:])\n",
    "                \n",
    "        #         print(res)\n",
    "        # return list(res)\n",
    "\n",
    "        ans = [\"\"]\n",
    "        for i, c in enumerate(s):\n",
    "            if c.isalpha():\n",
    "                ans = [a + c.lower() for a in ans] + [a + c.upper() for a in ans]\n",
    "            else:\n",
    "                ans = [a + c for a in ans]\n",
    "            print(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        path = []\n",
    "        n = len(s)\n",
    "        \n",
    "        def dfs(i: int):\n",
    "            if i == n:\n",
    "                res.append(''.join(path))\n",
    "                return\n",
    "            \n",
    "            if s[i].isdigit():\n",
    "                path.append(s[i])\n",
    "                dfs(i + 1)\n",
    "                path.pop()\n",
    "            else:\n",
    "                path.append(s[i])\n",
    "                dfs(i + 1)\n",
    "                path.pop()\n",
    "\n",
    "                path.append(s[i].swapcase())\n",
    "                dfs(i + 1)\n",
    "                path.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        # ans = []\n",
    "        # n = len(s)\n",
    "\n",
    "        # def dfs(s, pos):\n",
    "        #     while pos <len(s) and s[pos].isdigit():\n",
    "        #         pos += 1\n",
    "        #     if pos == n:\n",
    "        #         ans.append(''.join(s))\n",
    "        #         return\n",
    "\n",
    "        #     dfs(s, pos+1)\n",
    "        #     s[pos] = s[pos].swapcase()\n",
    "        #     dfs(s, pos+1)\n",
    "        #     s[pos] = s[pos].swapcase()\n",
    "        # dfs(list(s), 0)\n",
    "        # return ans\n",
    "\n",
    "        ans = []\n",
    "        path = []\n",
    "        n = len(s)\n",
    "        s = list(s)\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                ans.append(''.join(path))\n",
    "                return \n",
    "\n",
    "            if s[i].isdigit():\n",
    "                path.append(''.join(s[i]))\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "\n",
    "            else:\n",
    "                path.append(''.join(s[i].lower()))\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "                path.append(''.join(s[i].upper()))\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "            \n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        lst=list(s)\n",
    "        n=len(lst)\n",
    "        ret,path=[],lst.copy()\n",
    "        indexs=[i for i in range(n) if lst[i].isalpha()]\n",
    "        m=len(indexs)\n",
    "        def dfs(i):\n",
    "            if i==m:\n",
    "                ret.append(''.join(path))\n",
    "                return\n",
    "            path[indexs[i]]=path[indexs[i]].swapcase()\n",
    "            dfs(i+1)\n",
    "            path[indexs[i]]=path[indexs[i]].swapcase()\n",
    "            dfs(i+1)\n",
    "        dfs(0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        arr = list(s)\n",
    "        ans = []\n",
    "        mark = []\n",
    "        def dfs(index):\n",
    "            if len(mark) == len(s):\n",
    "                ans.append(\"\".join(mark))\n",
    "                return\n",
    "            if arr[index].isdigit():\n",
    "                mark.append(arr[index])\n",
    "                dfs(index + 1)\n",
    "                mark.pop()\n",
    "            else:\n",
    "                mark.append(arr[index])\n",
    "                dfs(index + 1)\n",
    "                mark.pop()\n",
    "                mark.append(arr[index].swapcase())\n",
    "                dfs(index + 1)\n",
    "                mark.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        path = list(s)\n",
    "        n = len(s)\n",
    "\n",
    "        def backtrack(i: int):\n",
    "            while i < n and s[i].isdigit():\n",
    "                i += 1\n",
    "\n",
    "            if i == n:\n",
    "                ans.append(''.join(path.copy()))\n",
    "                return\n",
    "\n",
    "            backtrack(i + 1)\n",
    "\n",
    "            path[i] = path[i].swapcase()\n",
    "            backtrack(i + 1)\n",
    "            path[i] = path[i].swapcase()\n",
    "\n",
    "        backtrack(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        lst=list(s)\n",
    "        n=len(lst)\n",
    "        ret,path=[],lst.copy()\n",
    "        indexs=[i for i in range(n) if lst[i].isalpha()]\n",
    "        m=len(indexs)\n",
    "        def dfs(i):\n",
    "            if i==m:\n",
    "                ret.append(''.join(path))\n",
    "                return\n",
    "            path[indexs[i]]=path[indexs[i]].swapcase()\n",
    "            dfs(i+1)\n",
    "            path[indexs[i]]=path[indexs[i]].swapcase()\n",
    "            dfs(i+1)\n",
    "        dfs(0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        n = len(s)\n",
    "        def dfs(i: int) -> None:\n",
    "            if i == n:\n",
    "                ans.append(''.join(path.copy()))\n",
    "                return\n",
    "            if s[i].isdigit():\n",
    "                path.append(s[i])\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "            else:\n",
    "                path.append(s[i].lower())\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "\n",
    "                path.append(s[i].upper())\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        numcase = set([str(i) for i in range(10)])\n",
    "        n = len(s)\n",
    "        path = []\n",
    "        ans = []\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                ans.append(\"\".join(path.copy()))\n",
    "                return\n",
    "            if s[i] in numcase:\n",
    "                path.append(s[i])\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "            else:\n",
    "                path.append(str.upper(s[i]))\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "                path.append(str.lower(s[i]))\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = [[]]\n",
    "        for ch in s:\n",
    "            n = len(ans)\n",
    "            if ch.isalpha():\n",
    "                for i in range(n):\n",
    "                    ans.append(ans[i][:])\n",
    "                    ans[i].append(ch.lower())\n",
    "                    ans[n+i].append(ch.upper())\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    ans[i].append(ch)\n",
    "        return [''.join(x) for x in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, S: str) -> List[str]:\n",
    "        l=[[]]\n",
    "        for i in S:\n",
    "            print(l)\n",
    "            if i.isdigit():\n",
    "                for j in l:\n",
    "                    j.append(i)\n",
    "            else:\n",
    "                t=copy.deepcopy(l)\n",
    "                for j in l:\n",
    "                    j.append(i.lower())\n",
    "                for k in t:\n",
    "                    k.append(i.upper())\n",
    "                l+=t\n",
    "        l2=[\"\".join(i) for i in l]\n",
    "        return l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        result = []\n",
    "        n = len(s)\n",
    "        path = []\n",
    "        def dfs(index):\n",
    "            if index == n:\n",
    "                if \"\".join(path) not in result:\n",
    "                    result.append(\"\".join(path))\n",
    "                return\n",
    "            if s[index].isdigit():\n",
    "                path.append(s[index])\n",
    "                dfs(index+1)\n",
    "            else:\n",
    "                word = s[index]\n",
    "                path.append(word.lower())\n",
    "                dfs(index+1)\n",
    "                path.pop()\n",
    "                path.append(word.upper())\n",
    "                dfs(index+1)\n",
    "            path.pop()\n",
    "        dfs(0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        path = []\n",
    "        n = len(s)\n",
    "        d = {}\n",
    "        a = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        b = 'abcdefghijklmnopqrstuvwxyz'.upper()\n",
    "        for aa, bb in zip(a, b):\n",
    "            d[aa] = bb\n",
    "            d[bb] = aa\n",
    "        def dfs(idx):\n",
    "            if idx == n:\n",
    "                res.append(''.join(path))\n",
    "                return\n",
    "            path.append(s[idx])\n",
    "            dfs(idx + 1)\n",
    "            path.pop()\n",
    "            if 'a' <= s[idx] <= 'z' or 'A' <= s[idx] <= 'Z':\n",
    "                path.append(d[s[idx]])\n",
    "                dfs(idx + 1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        def dfs(i, tmp):\n",
    "            if i == len(s): \n",
    "                res.append(\"\".join(tmp))\n",
    "      \n",
    "            else:\n",
    "                digit = s[i] \n",
    "\n",
    "                if digit.isalpha():\n",
    "\n",
    "                    tmp.append(digit.lower())\n",
    "                    dfs(i+1, tmp)\n",
    "                    tmp.pop()\n",
    "                    \n",
    "                    tmp.append(digit.upper())\n",
    "                    dfs(i+1, tmp)\n",
    "                    tmp.pop()\n",
    "     \n",
    "\n",
    "                else:\n",
    "                    tmp.append(digit)\n",
    "                    dfs(i+1, tmp)\n",
    "                    tmp.pop()\n",
    "                \n",
    "        dfs(0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        s = s + '\\n'\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        path = list(s)\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                ans.append(''.join(path[:-1]))\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                if s[j] >= '0' and s[j] <= '9':\n",
    "                    continue\n",
    "                if s[j] >= 'A' and s[j] <= 'z':\n",
    "                    if s[j] >= 'A' and s[j] <= 'Z':\n",
    "                        path[j] = s[j].lower()\n",
    "                    else:\n",
    "                        path[j] = s[j].upper()\n",
    "                    dfs(j + 1)\n",
    "                    path[j] = s[j]\n",
    "                else: # s[j] = '\\n'\n",
    "                    dfs(j + 1)\n",
    "                  \n",
    "        dfs(0)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        def getcomb(i, s):\n",
    "            if i==n:\n",
    "                res.add(s)\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                getcomb(j+1, s)\n",
    "                if s[j].isalpha():\n",
    "                    if s[j].isupper():\n",
    "                        getcomb(j+1, s[:j]+s[j].lower()+s[j+1:])\n",
    "                    else:\n",
    "                        getcomb(j+1, s[:j]+s[j].upper()+s[j+1:])\n",
    "        res = set()\n",
    "        getcomb(0, s)\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        path=list(s)\n",
    "        ans=[]\n",
    "        def dfs(i):\n",
    "            ans.append(\"\".join(path))\n",
    "            for j in range(i,n):\n",
    "                if path[j].isdigit(): continue       \n",
    "                path[j]=path[j].swapcase()\n",
    "                dfs(j+1)\n",
    "                path[j]=path[j].swapcase()\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        def backtrack(path, index, size):\n",
    "            if index == size:\n",
    "                res.append(''.join(path))\n",
    "                return\n",
    "            if s[index].isdigit():\n",
    "                path.append(s[index])\n",
    "                backtrack(path, index + 1, size)\n",
    "                path.pop()\n",
    "            else:\n",
    "                path.append(s[index].lower())\n",
    "                backtrack(path, index + 1, size)\n",
    "                path.pop()\n",
    "\n",
    "                path.append(s[index].upper())\n",
    "                backtrack(path, index + 1, size)\n",
    "                path.pop()\n",
    "\n",
    "        size = len(s)\n",
    "        res = []\n",
    "        backtrack([], 0, size)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        path = list(s)\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                ans.append(''.join(path.copy()))\n",
    "                return \n",
    "            if path[i].isdigit():\n",
    "                dfs(i+1)\n",
    "            else:\n",
    "                # 不变\n",
    "                dfs(i+1)\n",
    "\n",
    "                # 变\n",
    "                path[i] = path[i].swapcase()\n",
    "                dfs(i+1)\n",
    "                path[i] = path[i].swapcase()\n",
    "        dfs(0)\n",
    "        return ans  \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        path = \"\"\n",
    "        n = len(s)\n",
    "        def dfs(i):\n",
    "            nonlocal path\n",
    "            if i == n:\n",
    "                ans.append(path)\n",
    "                return\n",
    "            if s[i].isalpha():\n",
    "                path += s[i].lower()\n",
    "                dfs(i+1)\n",
    "                path = path[:-1]\n",
    "\n",
    "                path += s[i].upper()\n",
    "                dfs(i+1)\n",
    "                path = path[:-1]\n",
    "            else:\n",
    "                path += s[i]\n",
    "                dfs(i+1)\n",
    "                path = path[:-1]\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        ans, path = [], []\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "\n",
    "            path.append(s[i])\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "\n",
    "            if s[i].isupper():\n",
    "                path.append(s[i].lower())\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "            elif s[i].islower():\n",
    "                path.append(s[i].upper())\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans=[]\n",
    "        s1=''\n",
    "        n=len(s)\n",
    "        def func(a):\n",
    "            nonlocal s1\n",
    "            if len(s1)==len(s):\n",
    "                ans.append(s1)\n",
    "                return\n",
    "            for i in range(a,n):\n",
    "                if s[i].isalpha():\n",
    "                    s1=s1+s[i].lower()\n",
    "                    func(i+1)\n",
    "                    s1=s1[:-1]\n",
    "                    s1=s1+s[i].upper()\n",
    "                    func(i+1)\n",
    "                    s1=s1[:-1]\n",
    "                else:\n",
    "                    s1=s1+s[i]\n",
    "                    func(i+1)\n",
    "                    s1=s1[:-1]\n",
    "        func(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        res = []\n",
    "\n",
    "        def dfs(index, cache):\n",
    "            if index >= n:\n",
    "                res.append(cache)\n",
    "                return\n",
    "            if 'a' <= s[index] <= 'z':\n",
    "                dfs(index + 1, cache + s[index])\n",
    "                dfs(index + 1, cache + s[index].upper())\n",
    "\n",
    "            elif 'A' <= s[index] <= 'Z':\n",
    "                dfs(index + 1, cache + s[index])\n",
    "                dfs(index + 1, cache + s[index].lower())\n",
    "            else:\n",
    "                dfs(index + 1, cache + s[index])\n",
    "\n",
    "        dfs(0, \"\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        n = len(s)\n",
    "        path = []\n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "            if s[i].isalpha():\n",
    "                path.append(s[i].lower())\n",
    "                f(i+1)\n",
    "                path.pop()\n",
    "                path.append(s[i].upper())\n",
    "                f(i+1)\n",
    "                path.pop()\n",
    "            else:\n",
    "                path.append(s[i])\n",
    "                f(i+1)\n",
    "                path.pop()\n",
    "        f(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        path = list(s)\n",
    "\n",
    "        def dfs(i):\n",
    "            ans.append(''.join(path))\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                if s[j].isalpha():\n",
    "                    path[j] = path[j].swapcase()\n",
    "                    dfs(j+1)\n",
    "                    path[j] = path[j].swapcase()\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        res = []\n",
    "        def backtrack(path, idx):\n",
    "            if len(path) == n:\n",
    "                res.append(path)\n",
    "                return\n",
    "            elif len(path) > n:\n",
    "                return\n",
    "            \n",
    "            if 'a' <= s[idx] <= 'z' or 'A' <= s[idx] <= 'Z':\n",
    "                backtrack(path+s[idx].upper(), idx+1)\n",
    "                backtrack(path+s[idx].lower(), idx+1)\n",
    "            else:\n",
    "                backtrack(path+s[idx], idx+1)\n",
    "        backtrack(\"\", 0)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        path = list(s)\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                ans.append(''.join(path))\n",
    "                return \n",
    "\n",
    "            if s[i].isnumeric():\n",
    "                dfs(i+1)\n",
    "            else:\n",
    "                path[i] = s[i].lower()\n",
    "                dfs(i+1)\n",
    "\n",
    "                path[i] = s[i].upper()\n",
    "                dfs(i+1)\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        # path = []\n",
    "        # # 选或不选\n",
    "        # def dfs(i):\n",
    "        #     if i == n:\n",
    "        #         ans.append(''.join(path))\n",
    "        #         return\n",
    "\n",
    "        #     path.append(s[i])\n",
    "        #     dfs(i+1)\n",
    "        #     path.pop()\n",
    "\n",
    "        #     if s[i].isupper():\n",
    "        #         path.append(s[i].lower())\n",
    "        #         dfs(i+1)\n",
    "        #         path.pop()\n",
    "        #     elif s[i].islower():\n",
    "        #         path.append(s[i].upper())\n",
    "        #         dfs(i+1)\n",
    "        #         path.pop()\n",
    "        # dfs(0)\n",
    "\n",
    "        path = [c for c in s]\n",
    "        # 枚举选哪个\n",
    "        def dfs(i):\n",
    "            ans.append(''.join(path))            \n",
    "            for j in range(i, n):\n",
    "                if s[j].isdigit():\n",
    "                    continue\n",
    "                else:\n",
    "                    if s[j].islower():\n",
    "                        path[j] = s[j].upper()\n",
    "                    elif s[j].isupper():\n",
    "                        path[j] = s[j].lower()\n",
    "                    dfs(j+1)  \n",
    "                    path[j] = s[j]   \n",
    "        dfs(0)    \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                ans.append(\"\".join(path.copy()))\n",
    "                return\n",
    "            if s[i].isdigit():\n",
    "                path.append(s[i])\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "            else:\n",
    "                path.append(s[i].lower())\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "                \n",
    "                path.append(s[i].upper())\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        n = len(s)\n",
    "        path = s\n",
    "        def dfs(u):\n",
    "            nonlocal path\n",
    "            ans.append(path)\n",
    "            if u == n:\n",
    "                return\n",
    "            for j in range(u, n):\n",
    "                if path[j].isalpha():\n",
    "                    path = path[:j] + path[j].swapcase() + path[j+1:]\n",
    "                    dfs(j + 1)\n",
    "                    path = path[:j] + path[j].swapcase() + path[j+1:]\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        temp =[]\n",
    "        def dfs(i):\n",
    "            if i >= len(s):\n",
    "                res.append(''.join(temp))\n",
    "                return\n",
    "            else:\n",
    "                if s[i].isalpha():\n",
    "                    temp.append(s[i].lower())\n",
    "                    dfs(i+1)\n",
    "                    temp.pop()\n",
    "                    temp.append(s[i].upper())\n",
    "                    dfs(i+1)\n",
    "                    temp.pop()\n",
    "                else:\n",
    "                    temp.append(s[i])\n",
    "                    dfs(i+1)\n",
    "                    temp.pop()\n",
    "        dfs(0)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "\n",
    "        ret = []\n",
    "        N = len(s)\n",
    "        def dfs(path, i):\n",
    "            if i == N:\n",
    "                ret.append(path)\n",
    "                return\n",
    "            if \"a\" <= s[i] <= \"z\":\n",
    "                dfs(path + s[i], i + 1)\n",
    "                dfs(path + s[i].upper(), i + 1)\n",
    "            elif \"A\" <= s[i] <= \"Z\":\n",
    "                dfs(path + s[i], i + 1)\n",
    "                dfs(path + s[i].lower(), i + 1)\n",
    "            else:\n",
    "                dfs(path + s[i], i + 1)\n",
    "        \n",
    "        dfs(\"\", 0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans=[]\n",
    "        n=len(s)\n",
    "        def dfs(k,tmp):\n",
    "            if k>=n:\n",
    "                ans.append(tmp[:])\n",
    "                return\n",
    "            if s[k].isdigit():\n",
    "                dfs(k+1,tmp+s[k])\n",
    "            else:\n",
    "                dfs(k+1,tmp+s[k].upper())\n",
    "                dfs(k+1,tmp+s[k].lower())\n",
    "        dfs(0,\"\")\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\r\n",
    "        res = []\r\n",
    "        path = [''] * (n := len(s))\r\n",
    "\r\n",
    "        def dfs(i):\r\n",
    "            if i == n:\r\n",
    "                res.append(''.join(path[x] if path[x] else s[x] for x in range(n)))\r\n",
    "                return\r\n",
    "\r\n",
    "            dfs(i + 1)\r\n",
    "            if s[i].isalpha():\r\n",
    "                path[i] = chr(ord(s[i]) ^ 32)\r\n",
    "                dfs(i + 1)\r\n",
    "                path[i] = chr(ord(path[i]) ^ 32)\r\n",
    "\r\n",
    "        dfs(0)\r\n",
    "        return res\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "\n",
    "        def traverse(path, index):\n",
    "            if len(path) == len(s):\n",
    "                ans.append(\"\".join(path))\n",
    "                return\n",
    "            for i in range(index, len(s)):\n",
    "                if s[i].isalpha():\n",
    "                    path.append(s[i])\n",
    "                    traverse(path, i + 1)\n",
    "                    path.pop()\n",
    "                    if s[i].islower():\n",
    "                        path.append(s[i].upper())\n",
    "                        traverse(path, i + 1)\n",
    "                        path.pop()\n",
    "                    else:\n",
    "                        path.append(s[i].lower())\n",
    "                        traverse(path, i + 1)\n",
    "                        path.pop()\n",
    "                else:\n",
    "                    path.append(s[i])\n",
    "                    traverse(path, i + 1)\n",
    "                    path.pop()\n",
    "        traverse([], 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans, path = [], []\n",
    "        n = len(s)\n",
    "        def dfs(i):\n",
    "            if len(path.copy()) == n:\n",
    "                ans.append(''.join(path.copy()))\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                if s[j].isdigit():\n",
    "                    path.append(s[j])\n",
    "                    dfs(j+1)\n",
    "                    path.pop()\n",
    "                else:\n",
    "                    path.append(s[j].lower())\n",
    "                    dfs(j+1)\n",
    "                    path.pop()\n",
    "\n",
    "                    path.append(s[j].upper())\n",
    "                    dfs(j+1)\n",
    "                    path.pop()\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        def dfs(s: List[str], pos: int) -> None:\n",
    "            while pos < len(s) and s[pos].isdigit():\n",
    "                pos += 1\n",
    "            if pos == len(s):\n",
    "                ans.append(''.join(s))\n",
    "                return\n",
    "            dfs(s, pos + 1)\n",
    "            s[pos] = s[pos].swapcase()\n",
    "            dfs(s, pos + 1)\n",
    "            s[pos] = s[pos].swapcase()\n",
    "        dfs(list(s), 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        # 方法一：从答案的角度\n",
    "        # res, path, n = [], list(s), len(s)\n",
    "        # def dfs(i):\n",
    "        #     res.append(\"\".join(path))\n",
    "        #     for j in range(i, n):\n",
    "        #         if s[j].isalpha():\n",
    "        #             path[j] = path[j].swapcase()\n",
    "        #             dfs(j+1)\n",
    "        #             path[j] = path[j].swapcase()\n",
    "        \n",
    "        # dfs(0)\n",
    "        # return res\n",
    "        # 方法二：从输入的角度\n",
    "        n = len(s)\n",
    "        res, path = [], list(s)\n",
    "        def dfs(i):\n",
    "            if i==n:\n",
    "                res.append(\"\".join(path))\n",
    "                return\n",
    "            # 不选\n",
    "            dfs(i+1)\n",
    "            # 选\n",
    "            if s[i].isalpha():\n",
    "                path[i] = path[i].swapcase()\n",
    "                dfs(i+1)\n",
    "                path[i] = path[i].swapcase()\n",
    "\n",
    "        dfs(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        # 方法一：从答案的角度\n",
    "        # res, path, n = [], list(s), len(s)\n",
    "        # def dfs(i):\n",
    "        #     res.append(\"\".join(path))\n",
    "        #     for j in range(i, n):\n",
    "        #         if s[j].isalpha():\n",
    "        #             path[j] = path[j].swapcase()\n",
    "        #             dfs(j+1)\n",
    "        #             path[j] = path[j].swapcase()\n",
    "        \n",
    "        # dfs(0)\n",
    "        # return res\n",
    "        # 方法二：从输入的角度\n",
    "        n = len(s)\n",
    "        res, path = [], list(s)\n",
    "        def dfs(i):\n",
    "            if i==n:\n",
    "                res.append(\"\".join(path))\n",
    "                return\n",
    "            # 不选\n",
    "            dfs(i+1)\n",
    "            # 选\n",
    "            if s[i].isalpha():\n",
    "                path[i] = path[i].swapcase()\n",
    "                dfs(i+1)\n",
    "                path[i] = path[i].swapcase()\n",
    "\n",
    "        dfs(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        res=[]\n",
    "        #path=[]\n",
    "        def dfs(i,path):\n",
    "            if  i==len(s): ###\n",
    "                res.append(\"\".join(path.copy()))\n",
    "                return ### 这里要return ！！！！！ \n",
    "            if s[i].isdigit(): \n",
    "                dfs(i+1,path+[s[i]])\n",
    "            else:\n",
    "                dfs(i+1,path+[s[i].upper()])\n",
    "                dfs(i+1,path+[s[i].lower()])\n",
    "        dfs(0,[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\r\n",
    "        n = len(s)\r\n",
    "        ans = []\r\n",
    "        tmp = []\r\n",
    "        def dfs(index):\r\n",
    "            if index == n:\r\n",
    "                ans.append(''.join(tmp))\r\n",
    "                return\r\n",
    "            ch = s[index]\r\n",
    "            \r\n",
    "            tmp.append(ch)\r\n",
    "            dfs(index + 1)\r\n",
    "            tmp.pop(-1)\r\n",
    "            \r\n",
    "            if 'a' <= ch <= 'z':\r\n",
    "                ch = ch.upper()\r\n",
    "            elif 'A' <= ch <= 'Z':\r\n",
    "                ch = ch.lower()\r\n",
    "            else:\r\n",
    "                return\r\n",
    "            tmp.append(ch)\r\n",
    "            dfs(index + 1)\r\n",
    "            tmp.pop(-1)\r\n",
    "        dfs(0)\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        def dfs(s: List[str], pos: int) -> None:\n",
    "            while pos < len(s) and s[pos].isdigit():\n",
    "                pos += 1\n",
    "            if pos == len(s):\n",
    "                ans.append(''.join(s))\n",
    "                return\n",
    "            dfs(s, pos + 1)\n",
    "            s[pos] = s[pos].swapcase()\n",
    "            dfs(s, pos + 1)\n",
    "            s[pos] = s[pos].swapcase()\n",
    "        dfs(list(s), 0)\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
